package 动态规划专项训练.动态规划训练1;

/**63.不同路径II
 * 坐标型动态规划
 * @author zx
 * @create 2022-03-30 17:08
 */
public class Num63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m == 0){
            return 0;
        }
        int n = obstacleGrid[0].length;
        if(n == 0){
            return 0;
        }
        int[][] f = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                if(obstacleGrid[i][j] == 1){
                    f[i][j] = 0;
                }else{
                    //初始化条件
                    if(i == 0 && j == 0){
                        f[i][j] = 1;
                    }else{
                        //if(i == 0) f[i][j] = f[i][j - 1];这样写有两行代码,复杂点
                        f[i][j] = 0;//为了同时处理第一行第一列,
                        if(i - 1 >= 0){
                            f[i][j] += f[i - 1][j];
                        }
                        if(j - 1 >= 0){
                            f[i][j] += f[i][j - 1];
                        }
                    }
                }
            }
        }
        return f[m - 1][n - 1];
    }
}
